
//从前序与中序遍历序列构造二叉树
class Solution {
public:
    unordered_map<int,int> hashIndex;
    int begin = 0;
    TreeNode* recursion(const vector<int>& preorder,int left,int right)
    {
        if(left > right){
            return nullptr;
        }
        int val = preorder[begin++];
        int index = hashIndex[val];
        TreeNode* newNode = new TreeNode(val);
        newNode->left = recursion(preorder,left,index-1);
        newNode->right = recursion(preorder,index+1,right);
        return newNode;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        //通过前序遍历的值获得在中序遍历中该值所在的位置
        for(int i = 0;i < inorder.size();++i)
        {
            hashIndex[inorder[i]] = i;
        }
        return recursion(preorder,0,preorder.size()-1);
    }
};